package main

import (
	"fmt"
)

//接口
type molder interface{
	demo_mold(array []int, length int)
}

//归并排序结构体
type merges_mold struct{
	
}

//归并排序
func (merge merges_mold) demo_mold(array []int, length int){
	merge_array := merge_mold(array, length)
	show_array(merge_array)
}

func merge_mold(array []int, length int) []int {
	if length==1 {
		return array
	}

	middle :=length/2
	left := array[0:middle]
	right := array[middle:]

	return merge(merge_mold(left,len(left)),merge_mold(right,len(right)))
}

func merge(left []int, right []int) []int{
	var result []int
	for len(left) != 0 && len(right) !=0 {
		if left[0] <= right[0] {
			result = append(result, left[0])
			left = left[1:]			
		}else{
			result = append(result, right[0])
			right = right[1:]
		}
	}
	for len(left) !=0 {
		result = append(result, left[0])
		left = left[1:]
	}
	for len(right) !=0 {
		result = append(result, right[0])
		right = right[1:]
	}
	return result
}

type counter_mold struct{

}
//counter_mold结构体计数排序的实现
func (counter counter_mold) demo_mold(array []int,length int){
	counter_array := counte_mold(array, length)
	show_array(counter_array)
}

//计数排序方法
func counte_mold(array []int, length int) []int{
	max := Max(array,length)
	count_length := max + 1
	counter_array := make([]int, count_length)
	index := 0
	for i := 0; i < length; i++ {
		counter_array[array[i]] +=1
	}
	for j := 0; j < count_length; j++ {
		for counter_array[j] > 0 {
			array[index] = j
			index +=1
			counter_array[j] -= 1
		}
	}
	return array
}

func Max(array []int, length int) int {
	max := array[0]
	for i := 0; i < length; i++ {
		if array[i] > max {
			max = array[i]
		}
	}
	return max
}

//堆排序结构体
type heap_mold struct{

}

func (heap heap_mold) demo_mold(array []int, length int){
	heap_array := heaper_mold(array,length)
	show_array(heap_array)
}

func heaper_mold(array []int, length int) []int{
	max_heap(array, length)
	for i := length - 1; i >= 0; i-- {
		swap(array, 0, i)
		length -= 1
		heap_find(array, 0, length)
	}
	return array
}

func max_heap(array []int, length int){
	for i := length /2; i >= 0; i-- {
		heap_find(array, i, length)
	}
}

func heap_find(array []int, i int, length int){
	left := 2*i + 1
	right := 2*i + 2
	biggest := i
	if left <length && array[left] > array[biggest] {
		biggest = left
	}
	if right <length && array[right] > array[biggest] {
		biggest = right
	}
	if biggest != i {
		swap(array,i, biggest)
		heap_find(array, biggest, length)

	}
}

func swap(array []int, i int, j int){
	array[i], array[j] = array[j], array[i]
}

func show_array(array []int){
	fmt.Println(array)
}

//策略模式
type moldselect struct{
	array []int
	selct molder
}

func (s *moldselect) setarray(arr []int) {
	s.array = arr
	fmt.Print("原数组:")
	show_array((s.array))
}

func (s *moldselect) setselct(sel molder){
	s.selct = sel
}

func (s *moldselect) demo_mold(){
	length := len(s.array)
	s.selct.demo_mold(s.array,length)
}

func main(){
	fmt.Println("测试数据:")
	array := []int{1,2,3,7,5,9,20,22}
	mold := moldselect{}
	mold.setarray(array)

	fmt.Println("归并排序:")
	mold.setselct(merges_mold{})
	mold.demo_mold()

	fmt.Println("堆排序:")
	mold.setselct(heap_mold{})
	mold.demo_mold()

	fmt.Println("计数排序:")
	mold.setselct(counter_mold{})
	mold.demo_mold()

	
}